/*
 * @lc app=leetcode.cn id=718 lang=javascript
 *
 * [718] 最长重复子数组
 *
 * https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/description/
 *
 * algorithms
 * Medium (45.25%)
 * Likes:    73
 * Dislikes: 0
 * Total Accepted:    3.8K
 * Total Submissions: 8.4K
 * Testcase Example:  '[1,2,3,2,1]\n[3,2,1,4,7]'
 *
 * 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
 * 
 * 示例 1:
 * 
 * 
 * 输入:
 * A: [1,2,3,2,1]
 * B: [3,2,1,4,7]
 * 输出: 3
 * 解释: 
 * 长度最长的公共子数组是 [3, 2, 1]。
 * 
 * 
 * 说明:
 * 
 * 
 * 1 <= len(A), len(B) <= 1000
 * 0 <= A[i], B[i] < 100
 * 
 * 
 */
/**
 * @param {number[]} A
 * @param {number[]} B
 * @return {number}
 */

// 该题与求最长公共子串一样, 在寻找最长子串的过程中可以利用已经作出判断的更小的子串;
// 也就是在判断一个子串是否重复的时候可以利用上一步对更短子串的判断结果, 可分解为子问题, 且与子问题之间有递推关系;
// 动态规划关键在于找到这个递推:
// S1, S2表示两个字符串, L[i, j]表示以S1[i]和S2[j]为结尾的两个子串的最大公共长度,
// 递推关系为L[i+1, j+1] = S1[i] === S2[j] ? L[i, j]+1 : 0

// 为什么不用S1[i] S2[j]最为开头的两个子串来左匹配? 因为动态规划需要通过子问题来递推, 用作子串开头的话, 且从左到右来计算这个子串
// 的最大公共长度, 需要右边还未知的子串信息.
var findLength = function (A, B) {
    if (!A.length || !B.length) return []
    let la = A.length,
        lb = B.length
    let sum = 0
    let L = new Array(la)
    for (let k = 0; k < la; k++) L[k] = new Array(lb)

    for (let i = 0; i < la; i++) {
        for (let j = 0; j < lb; j++) {
            if (A[i] === B[j]) {
                L[i][j] = (i - 1 >= 0 && j - 1 >= 0 ? L[i - 1][j - 1] : 0) + 1
                if (L[i][j] > sum) sum = L[i][j]
                continue
            }
            L[i][j] = 0
        }
    }
    return sum
};

// let re = findLength([1,2,3,2,1], [3,2,1,4,7])
// console.log(re[0])
// console.log(re[1])